从0打卡leetcode之day 3 -- 最大子序列和

发表于 | 分类于 | 0 comments | 浏览 次

前言

深知自己在算法方面上很菜，于是打算通过打卡的方式，逼自己一把。每天在leetcode上打卡，并且把自己的想法分享出来。这将是一段漫长而又艰辛的旅程。如果你也想和我一起走上一条充满艰辛的航路，那么，别犹豫了，上车吧，一起学习一起探讨。

从零打卡leetcode之day 3

1
2
3
4
5
6
7
题目描述：
给定一个int类型的数组，求最大子序列的和。
也就是说，从这个数组中截取一个子数组，这个子数组的元素和最大。

例如：
-1 20 -4 14 -4 -2 
这个数组的最大字序列和为30。即20 -4 14。

解题

1.初级版解法

对于这道题，其实我们可以采取遍历所有可能的组合，然后再比较哪种组合的和最大。

也就是说，我们可以找出所有子序列，然后逐个比较。代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int solve(int[] arrs){

    int max = 0;//用来存放目标子序列的和

    int temp = 0;//用来存每个子序列的和

    for(int i = 0; i < arrs.length; i++){

        for(int j = i; j < arrs.length; j++){
        
            temp = 0;
            
            //计算子序列的和
            for(int k = 0; k < arrs.length; k++){
                temp += arrs[k];
            }
            //进行比较
            if(temp > max){
                max = temp;
            }
            
        }
    }
    
    return max;
}`

在这三个循环中，外面两个循环枚举出所有子序列，第三个循环计算子序列的和。

看到三个for循环，时间复杂度的O(n3)。这速度，实在是太慢了。我们来优化优化。

2.进阶版

其实，你仔细看一下里面的那两层for循环，会发现其实可以把它们合并成一个for循环的。

也就是说，我们可以在枚举所有子序列的过程中，是可以一边进行数据处理的。还是直接看代码好理解点。如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int solve2(int[] arrs){
    
    int max = 0; 
    
    int temp = 0;
    
    for(int i = 0; i < arrs.length; i++){
        
        temp = 0;
        
        for(int j = i; j < arrs.length; j++){
            
            //一边处理数据
            temp += arrs[j];
            
            //进行比较选择
            
            if(max < temp){
                
                max = temp;
            }
        }
    }
    
    return temp;
}

该方法用了两个for循环，时间复杂度为O(n2)，相对来说好了一点。

3.再次优化进阶

这次，我们可以使用递归的思想来处理。递归最重要的就是要找到：

  1. 递归的结束条件
  2. 把问题分解成若干个子问题。

对于这道题，其实我们可以把序列分成左右两部分。那么，最大子序列和的位置会出现在以下三种情况：

  1. 子序列完全在左半部分。
  2. 子序列完全在右半部分。
  3. 一部分在左，一部分在右。

所以我们只要分别求出左半部分的最大子序列和、右半部分的最大子序列和(注意，问题已经转化为求左右两部分的最大子序列和了，也就是说问题被分解成若干子问题了)、以及跨越左右两部分的最大子序列和。最后比较三者之中哪个比较大就可以了。

如何求解左半部分和右半部分的最大子序列？

其实道理一样，把左半部分和右半部分再次分解左右两部分就可以了。

那么，如何求解跨越左右两部分的最大子序列呢？

其实只要求出包含左半部分中最右边元素的子序列的最大和，以及求出包含右半部分中最左边元素的子序列的最大和，然后让两者相加，即可求出跨域左右两部分的最大子序列和了。

子问题已经分解出来了，那么递归的结束条件是什么？

我们把数组分成左右两部分，其实当左右两部分只有一个元素时，递归结束。

这道题的递归思路算是找出来了，不过，代码实现？假如你对递归不大熟悉的话，可能在实现上还是有那么点困难的。对于递归的学习，大家也可以看我写的关于递归与动态规划的几篇文章。

我就直接抛代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//递归版本
public int solve3(int[] arrs, int left, int right){
    int max = 0;

    //表示只有一个元素，无需在分解
    if(left == right){
        //为什么？因为低于0的数肯定不可以是最大值的
        //大不了最大值为0
        max = arrs[left] >= 0 ? arrs[left]:0;
    }else{

        int center = (left + right)/2;
        //求解左半部分最大子序列
        int leftMax = solve3(arrs, left, center);
        //求解右半部分最大子序列
        int rightMax = solve3(arrs, center+1, right);

        //求解kua跨越左右两部分的最大子序列
        //1.求包含左部分最右元素的最大和
        int l = 0;
        int l_max = 0;
        for(int i = center; i >= left; i--){
            l += arrs[i];
            if(l > l_max){
                l_max = l;
            }
        }

        //2.求包含右部分最左元素的最大和
        int r = 0;
        int r_max = 0;
        for(int i = center+1; i <= right; i++){
            r += arrs[i];
            if(r > r_max){
                r_max = r;
            }
        }
        //跨越左右两部分的最大子序列
         max = l_max + r_max;

        //取三者最大值
        if(max < leftMax) max = leftMax;
        if(max < rightMax) max = rightMax;
    }

    return max;
}

递归求解方法的时间复杂度为O(nlgn)。这速度，比第一种做法，不知道快了几个级别….

递归解法可以说是很快的了

但是，等等，我还是不满意…

4.最终版:动态规划

接下来的最终版，时间复杂度可以缩减到O(n), 虽然说是采用了动态规划的思想，不过，我觉得你没学过动态规划也可以看懂。

假如我给你

1
1 2 -4 5 6

五个元素，你在计算前面三个元素的时候，即

1 + 2 + -4 = -1

发现前面三个元素的和是小于0的，那么，这个

1 2 -4

的子序列我们还要吗？显然，这个子序列的和都小于0了，我们是可以直接淘汰的。因为如果还要这个子序列的话，它和后面的5一相加，结果变成了4，我们还不如让我们的目标子序列直接从5开始呢。

先看代码吧，可能反而会好理解点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//基于动态规划的思想
public int solve4(int[] arrs){
    int max = 0;//存放目标子序列的最大值
    int temp = 0;//存放子序列的最大值

    for(int i = 0; i < arrs.length; i++){
        temp += arrs[i];
        if(temp > max){
            max = temp;
        }else{
            //如果这个子序列的值小于0，那么淘汰
            //从后面的子序列开始算起
            if(temp < 0){
                temp = 0;
            }
         }
    }
    return max;
}

这道题不是leetcode上的题目，不过我觉得这道题很不错，所以拿出来分享给大家。

如果你有什么不大清楚的，欢迎微信群里讨论，当然也可以直接来问我勒。欢迎转发让更多人加入打卡行列勒。

如果这道题能对你有所帮助，不妨点个赞。哈哈